package dmsxl.huisu;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Author: Zhang Dongwei
 * Date: 2023/7/14 8:59
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 *
 * 注意：解集不能包含重复的组合。 
 */
public class hs8_40 {

    static List<List<Integer>> res = new ArrayList<>();
    static LinkedList<Integer> path = new LinkedList<>();
    static boolean[] used;
    static int sum = 0;

    public static void main(String[] args) {
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        res = combinationSum21(candidates, target);
        System.out.println(res);
    }

//    自己做的，没有去重
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        combineHelper(candidates, target, 0, 0);
        return res;
    }

    public static void combineHelper(int[] candidates, int target, int sum, int index){
        if (sum > target){
            return;
        }
        if (sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < candidates.length; i++){
            path.add(candidates[i]);
            sum += candidates[i];
            combineHelper(candidates, target, sum, i+1);
            path.removeLast();
            sum -= candidates[i];
        }
    }

    //    看视频答案，去重
    public static List<List<Integer>> combinationSum21(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.sort(candidates);
        combineHelper1(candidates, target, 0);
        return res;
    }

    public static void combineHelper1(int[] candidates, int target, int index){
        if (sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < candidates.length; i++){
            if (sum + candidates[i] > target){
                break;
            }
//            出现重复节点，同层的第一个节点已被访问过，跳过
            if (i > 0 && candidates[i] == candidates[i-1] && !used[i-1]){
                continue;
            }
            used[i] = true;
            path.add(candidates[i]);
            sum += candidates[i];
            combineHelper1(candidates, target, i+1);
            used[i] = false;
            path.removeLast();
            sum -= candidates[i];
        }
    }
}
